package binary_search.leetcode_74_mudium;

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = new int[]{};
        int[][] b = new int[][]{a};
        searchMatrix(b,1);

    }

    /**
     * 将m x n 的矩阵看作一个长度为 m x n 的数组，然后进行正常的二分查找即可。
     * <p>
     * 关键点在于，中间位置对应矩阵中的哪个元素？
     * row = pivotIndex / n
     * col = pivotIndex % n
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        //注意[ [] ] 这种数组情况，此时的数组长度为1， 下标0 为一个空数组
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        int left = 0;
        int right = m * n - 1;
        while (left < right) {
            int pivotIndex = left + (right - left) / 2;
            int pivotElement = matrix[pivotIndex / n][pivotIndex % n];
            if (pivotElement == target) {
                return true;
            } else if (pivotElement < target) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        return matrix[left / n][left % n] == target ? true : false;
    }
}
